package com.wtgroup.demo.leetcode.q016;

import java.util.Arrays;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/4/1 10:39
 */
public class S_LC_DoublePointer {
    public static void main(String[] args) {
        // int[] nums = {-1, 2, 1, -4};
        // int target = 1;
        int[] nums = {-3,-2,-5,3,-4};
        int target = -1;
        S_LC_DoublePointer exe = new S_LC_DoublePointer();
        int ans = exe.threeSumClosest(nums, target);
        System.out.println(ans);
    }

    /**
     * 双指针
     *
     */
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);

        int ans = 10000000; // ! 不能使用 INT_MAX , 可能会溢出, 导致结果错误
        // a,b,c 三数, a定, b,c 组合.
        for (int i = 0; i < nums.length; i++) {
            // 当前 a 和上次一样, 则没必要继续了
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            int a = nums[i];
            int lt = i+1, rt = nums.length-1;
            while (lt<rt) {
                int sum = a + nums[lt] + nums[rt];
                // 恰好相等, 没有比这个更合适了
                if (sum == target) {
                    return target;
                }
                if (Math.abs(target - sum) < Math.abs(target - ans)) {
                    ans = sum;
                }

                if (sum > target) {
                    // 右指针左移, 缩小值
                    // 同时, 略过相同的值
                    while (rt - 1 > lt && nums[rt - 1] == nums[rt]) {
                        --rt;
                    }
                    --rt;
                } else {
                    // 左指针右移, 扩大值
                    while (lt + 1 < rt && nums[lt + 1] == nums[lt]) {
                        ++lt;
                    }
                    ++lt;
                }
            }
        }

        return ans;
    }

}
